#include <iostream>
#include <unordered_map>

#include "common/utils.hpp"

/*
创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
*/
TreeNode* traversal(std::vector<int>& nums, int l, int r) {
    if (l >= r) return nullptr;

    int maxNum = INT_MIN;
    int maxNumIdx = 0;
    for (int i = l; i < r; i++) {
        if (nums[i] > maxNum) {
            maxNum = nums[i];
            maxNumIdx = i;
        }
    }
    TreeNode* node = new TreeNode(nums[maxNumIdx]);

    node->left = traversal(nums, l, maxNumIdx);
    node->right = traversal(nums, maxNumIdx + 1, r);

    return node;
}

TreeNode* constructMaximumBinaryTree(std::vector<int>& nums) {
    return traversal(nums, 0, nums.size());
}

extern TreeNode* commonRoot;

int main() {
    std::vector<int> nums = { 3, 2, 1, 6, 0, 5 };
    TreeNode* ret = constructMaximumBinaryTree(nums);
    printTreeNode(ret);
}